The present invention relates to lossless or near lossless image compression.
Many techniques, like pre-press imaging and medical imaging, demand very high quality. The images are often very large, say 2048xc3x972048xc3x973 pixels (e.g. in RGB format), thus requiring huge storage spaces and long transfer times. In order to alleviate these problems while keeping up with the xe2x80x9cno lossxe2x80x9d constraint, lossless compression techniques should be employed. While the compression ratio is rather small (of the order of 2-4), the benefits are quite worth the effort.
Theoretically, the minimal code length may be achieved by first transforming the color planes into three independent planes, decorrelating the planes in order to make them independent, and then compressing each plane optimally. That is why, most of the leading image compression techniques treat the color image (e.g. RGB) by this way, i.e. as three non-related gray-scale images. These include compression algorithms, such as:
BPTC [J. A. Robinson, xe2x80x9cEfficient General-Purpose Image Compression with Binary Tree Predictive Codingxe2x80x9d, IEEE transactions on Image Processing, vol. 6, no. 4, pp. 601-608, April 1997],
CALIC [X. Wu, N. Memon and K. Sayood, xe2x80x9cA Context-Based, Adaptive, Lossless/Nearly-Lossless Coding Scheme for Continuous-Tone Imagesxe2x80x9d, Proposal for the initial ISO/JPEG evaluation, http://www.csd.uwo.ca/faculty/wu/iso.ps, July 1995; and X. Wu et al, xe2x80x9cAn Algorithmic Study on Lossless Image Compressionxe2x80x9d, in Proceedings of the 1996 Data Compression Conference (Snowbird, Utah, USA), pp. 150-159, March 1996],
FELICS [P. G. Howard and J. S. Vitter, xe2x80x9cFast and Efficient Lossless Image Compressionxe2x80x9d, in Proceedings of the 1993 IEEE Data Compression Conference (Snowbird, Utah, USA), pp. 351-360, March 1993],
LOCO-I [M. J. Weinberger, G. Seroussi and G. Sapiro, xe2x80x9cLOCO-I: A Low Complexity, Context-Based, Lossless Image Compression Algorithmxe2x80x9d, in Proceedings of the 1996 IEEE Data Compression Conference (Snowbird, Utah, USA), pp. 140-149, March 1996], and
SPIHT [A. Said and W. A. Pearlman, xe2x80x9cA New Fast and Efficient Image Codec Based on Set Partitioning in Hierarchical Treesxe2x80x9d, IEEE transactions on Circuits and Systems for Video Technology, vol. 6, June 1996].
This approach, however, has not given promising results in practice. Due to its high complexity, these techniques requires high computational power.
Clearly, one can gain benefits in image compressing from exploiting the possible inter-color planes correlation. Therefore, another approach for treating the color image was employed. The main idea of this approach is to encode the current plane by using previous pixels from the same plane and from the other, already encoded, planes. The general concept is follows: first to encode one plane, and then to encode another plane by using the fact that the first plane is known already to the decoder, and finally, to encode the third plane by using the fact that both (first and second) planes are known to the decoder. This approach is implemented in Inter-Band CALIC algorithm, where the first, second and third color planes where the R, G and B planes, respectively (see X.
Wu, W. K. Choi, and N. Memon, xe2x80x9cLossless Interframe Image Compression via Context Modelingxe2x80x9d, in Proceedings of the 1998 Data Compression Conference (Snowbird, Utah, USA), pp. 378-387, March 1998). The approach of CALIC offers superior results, however, the method based on the algorithm of CALIC requires very high computational power.
Lossless image compression schemes often consist of two distinct and independent components: modeling and coding. This scheme of the lossless image compression is reflected in the block diagrame of FIG. 1. The dashed areas 11 in the image icons represent the scanned past data, on which the probability assignment is based, while the black dots 12 represent the pixel currently coded.
The modeling part can be formulated as an inductive inference problem, in which an image is observed pixel by pixel in some pre-defined order (i.e. raster scan). Hence, observing a color image is a simple generalization of a gray-scale image scan, where the pixels of different color planes are interlaced. The term pixel here denotes a monochrome picture element, whereas the term color-pixel denotes a color picture element (consisting of three pixels).
The first step of the modeling is a prediction step in which by knowing the past data X1=X1, X2, . . . . , Xi, the next pixel""s conditional distribution p(Xi+1|Xi) is estimated in order to predict a deterministic value for the next pixel Xi+1. Ideally, the code length contributed by Xi+1 is xe2x88x92log2 [p(Xi+1|X1)] bits, which averages to the entropy of the probabilistic model. On the next step of the modeling, one performs a determination of the context on which Xi+1 occurs. Indeed, a prediction of the next pixel using a small neighborhood is better performed when conditioned by contexts. If the image is not truly a stationary process, one expects it to be a mixture of different types of processes, which may be classified according to image texture and local smoothness. This is also treated by contexts, which condition the probabilistic behavior of the image. On the last step of the modeling a probabilistic model the prediction residual (the error value), conditioned on the context of Xi+1, is generated. The prediction residual (error) is obtained from subtraction of the predicted value from the actual value. The errors and probability distribution of the prediction error values are then coded to produce an output.
The coding part of the lossless image compression schemes of the modeled prediction residuals may be done by an arithmetic encoder [see J. Rissanen, xe2x80x9cGeneralized Kraft Inequality and Arithmetic Coding,xe2x80x9d IBM Journal on Recent Developments, vol. 20, no. 3, pp. 198-203, May 1976; and G. G. Langdon, Jr., xe2x80x9cAn Introduction to Arithmetic Coding,xe2x80x9d IBM Journal on Recent Developments, vol. 28, pp. 135-149, 1984], but this means a high complexity algorithm. Huffman coding of the prediction error [see D. A. Huffman, xe2x80x9cA Method for the Construction of Minimum Redundancy Codesxe2x80x9d, in Proceedings of IRE, vol. 40, pp. 1098-1101, 1952] is much simpler, but it results in lower performance.
A method based on the aforementioned concept of modeling, which overcomes many problems of coding was implemented in U.S. Pat. No. 5,680,129 and in U.S. Pat. No. 5,835,034 by Weinberger, Seroussi and Sapiro. They invented the LOCO-I algorithm forming the basis for the draft standard JPEG-LS of ISO, ISO/ITU ISO/IEC JTC1/SC29 WG1(JPEG/JBIG) for lossless and near-lossless compression of continuous-tone images, Draft International Standard DIS14495-1 (JPEG-LS), 1998. LOCO-I combines the simplicity of Huffman coding with the compression potential of context models. A small number of free statistical parameters is used in LOCO-I to approach the capability of much more complex universal context modeling techniques without the drawbacks of context-dilution. Such a context dilution can occur due to the exponential growth of the number of states with respect to the model""s order. Avoiding the dilution is achieved by using a small efficient context space along with the adaptive, symbol-wise, Golomb-Rice code, depending on a single-parameter probability distribution. Another useful feature of LOCO-I is the embedded alphabet extension (run-mode), which further reduces the code redundancy when encoding runs.
However, despite a big step forward in the compressing technique there is still a need in the art to provide an improved method for lossless image compression, especially for color images. Indeed, the most advanced technques such as aforementioned U.S. Pat. Nos. 5,680,129 and 5,835,034 deal mostly with intra-plane approach. Despite the authors of LOCO-I describe the possibility of both intra- and inter-plane correlation for component prediction, they offer only specific approach for inter-plane predictor, which is based on the arithmetic averaging given by Eq. (10) of U.S. Pat. Nos. 5,680,129 and 5,835,034.
These patents also do not consider using a more varied structure of contexts or adaptive strategies such as taking the best between several intra- and inter-plane predictors, and do not show how to use the benefits of the inter-plane correlation in context forming and coding. In addition, they do not address the problem of joint run length encoding images.
It would therefore be desirable to provide a novel compressor for colored images, which will combine the benefits of the prior-art methods while maintaining at least the same order of complexity.
According to the present invention, there is provided a Simple Inter Color Lossless Image Coder (hereinafter SICLIC) for the compression of colored images. The invention utilizes ideas from LOCO-I and includes three main blocks, such as selection of the predictor, context forming with bias cancellation and coding, but it implements predictors, context forming and encoder techniques that exploit the inter-component correlations in an effective and relatively computationally inexpensive manner.
According to one embodiment of the invention, the color image is treated as three interlaced gray level images. In contrast to LOCO, by this embodiment the predictor is selected on the basis on the right selection of the contribution of each color plane, as opposed to the degenerated approach of LOCO-I, wherein the simple arithmetic averaging of the contribution of color planes was employed. Moreover, according to the invention, herein proposed a use of more than one predictor and selecting on the fly the best one between the intra- and inter-plane predictors obtained as a weight average of contribution from different color planes.
By a way of one non-limiting example, the G plane can be treated first, as this yields a small improvement in compression. A prediction of pixels in the is R and B planes can be based on intra-color correlations as well as inter-color correlations. Thus, SICLIC combines both intra-color and inter-color prediction and coding. In contrast to the treatment of gray scale images, where the contexts are generated from the local previous pixels of the current pixel, color images require inter-color correlations, which capture the inter-color behavior of the images. As will be illustrated below, an example of inter-color correlation is based on construction of an inter-color neighborhood, which, in turn, is based on constructing differences between adjacent pixels in two gray level images.
Thus, in accordance with the invention, there is provided a method for obtaining substantially lossless compression of a color digitized image that is composed of three distinct gray level images, which correspond to respective distinct color planes; each of said gray level images includes pixels, the method comprising the steps of:
(a) compressing a first gray level image that corresponds to a first color plane, utilizing an intra-color prediction;
(b) for the second gray level image relative to said first gray level image, performing repeatedly:
(i) calculating a predicted value of a pixel on the basis of inter-color correlations between at least one adjacent pixel in the second gray level image and at least one adjacent element in the first gray level image;
(ii) comparing the predicted value and the real value of the element so as to produce residual value;
(iii) determining the context of said element;
(iv) quantizing said context;
(v) updating a quantized context related bias residue;
(vi) comparing the residual value and the bias residual value to produce a bias-free residual value; and
(vii) coding a value that depends upon said bias-free residual value,
(c) for the third gray level image, performing said steps b(i) to b(vii) relative to either or both of said first gray level image and second gray level image.
It should be noted that when referring to xe2x80x9cboth of said first gray level image and second gray level image,xe2x80x9d it may be construed as applying the specific steps to the third gray level image relative to the second gray level image and, further applying separately the specified steps to the third gray level image relative to the first gray level image. However, xe2x80x9cbothxe2x80x9d my also refer to the situation, in which the specified steps apply to some kind of combination of said first and said second gray level images. One has to bear in mind, that the same interpretation also applies to a situation, when more than three color planes are used.
After compression, the image may be transmitted to remote sites (e.g. via the Internet) for decoding and decompression.
It should be noted, that according to the invention there is proposed an improved approach for context forming and coding, which utilizes both the intra- and inter-color plane correlations. It deals with both the intra-color contexts and inter-color contexts, thereby allowing the distinction between the intra- and inter-predictors and selection of the best of them.
As well as the aforementioned LOCO-I, SICLIC processes the image in two modesxe2x80x94regular mode and run mode. Having described above the general structure of the regular mode, including selection of the predictor, context forming with bias cancellation and coding, there is further proposed an improvement for the run mode. The run mode is an enhancement for reducing code redundancy, and is aimed at encoding groups of adjacent identical pixels. Runs may occur simultaneously on all the color planes, but they may also occur on one of the color planes. To this end, SICLIC""s run mode deals with preferably (although not necessarily) both joint runs and disjoint runs. In order to obtain an efficient compressing special care is taken to ensure a proper treatment of joint runs, which occur simultaneously in all color planes.
In accordance with the invention, there is further provided a method of decompression of a color image composed of three distinct color planes using a decoder, the method comprising:
(i) retrieving the compressed color image; and
(ii) decoding at least one color pixel from data of compressed image, comprising the steps of:
xe2x80x83(a) determining the context of at least one pixel by performing the steps that include:
(1) providing intra-color and inter-color neighborhoods constructed on the basis of the intra-color and inter-color correlations, wherein the intra-color and inter-color neighborhoods are composed of intra-color pixels and inter-color elements; and
(2) determining the context of said pixel and element based on values of at least one gradient between at least two pixels and at least one gradient between at least two elements in said neighborhoods;
(iii) calculating predicted values of a pixel and element on the basis of inter-color correlation between at least two adjacent pixels and between at least two adjacent elements, wherein the adjacent pixel is at least one pixel of the intra-color correlation and the adjacent element is at least one element in the second gray level image and corresponding at least one adjacent element in the first gray level image;
(iv) accessing a context-specific code table and retrieving residual values from the table in response to encoded data, said residual values corresponding to intra- and inter-plane contexts;
(v) combining the residual values with the predicted values for at least one pixel and at least one element in order to obtain an actual value of said color pixel.
The present invention still further provides for a system for obtaining substantially lossless compression of a color digitized image that is composed of three distinct gray level images that correspond to respective distinct color planes; each of said gray level images includes pixels, the system comprising a processor of capable of performing the steps of:
(a) compressing a first gray level image that corresponds to a first color plane, utilizing an intra-color prediction;
(b) for the second gray level image relative to said first gray level image, performing repeatedly:
(i) calculating a predicted value of a pixel on the basis of inter-color correlations between at least one adjacent pixel in the second gray level image and at least one adjacent element in the first gray level image;
(ii) comparing the predicted value and the real value of the element so as to produce residual value;
(iii) determining the context of said element;
(iv) quantizing said context;
(v) updating a quantized context related bias residue;
(vi) comparing the residual value and the bias residual value to produce a bias-free residual value; and
(vii) coding a value that depends upon said bias-free residual value;
(c) for the third gray level image, performing said steps b(i) to b(vii) relative to either or both of said first gray level image and second gray level image.